#include "evenoddmergesort.h"
#include <algorithm>

// ------------------- CONSTRUCTORS AND DESTRUCTORS ----------------------
EvenOddMergeSort::EvenOddMergeSort(int threadCnt){
    this->threadCnt = threadCnt;
}

EvenOddMergeSort::~EvenOddMergeSort(){

}

//-------------------- PUBLIC METHODS ------------------------------------

// Sort items with EvenOddMergeSort algorithm
void EvenOddMergeSort::sort(Array * a){
    this->a = a->getArray();
    this->sortImpl(a->getCnt());
    this->a = NULL;
}

void EvenOddMergeSort::sortImpl(unsigned long cnt)
{
    int * arr = this->a;
    for (unsigned long m = 2; m <= cnt; m <<= 1)
    {
#pragma omp parallel for shared(arr, cnt, m) schedule(dynamic, threadCnt) num_threads(threadCnt)
        for (unsigned long low = 0; low < cnt; low += m)
        {
	    // Split
	    unsigned long subSize = m / 2;
	    int * ae = new int[subSize];
	    int * ao = new int[subSize];
	    for (unsigned long i = 0; i < subSize; i++)
	    {
		ae[i] = arr[low + 2 * i];
		ao[i] = arr[low + 2 * i + 1];
	    }
	    //Sort the odd and even subsequences
	    std::sort(ae, ae + subSize);
	    std::sort(ao, ao + subSize);
	    // Merge
	    arr[low] = ae[0];
	    for (unsigned long i = 1; i < subSize; i++)
	    {
		if (ae[i] <= ao[i - 1])
		{
		    arr[low + 2 * i - 1] = ae[i];
		    arr[low + 2 * i] = ao[i - 1];
		}
		else
		{
		    arr[low + 2 * i - 1] = ao[i - 1];
		    arr[low + 2 * i] = ae[i];
		}
	    }
	    arr[low + m - 1] = ao[subSize - 1];
        }
    }
}
